Printers which employ raster scan pixel displays are often called upon to represent filled polygonal shapes. The classical approach to contour "filling" of polygons is to process a set of polygon edge lists in scan-line order and from those lists, derive a set of interior horizontal line segments which are then printed as lines of black pixels.
With the onset of read/write frame stores and partial frame memories, processing time required for polygonal contour filling has been substantially improved. Newer algorithms typically plot a conventional vector outline into a single bit plane. Filling is then completed by processing the plane as though it were a large array. Thus, most of the execution time is spent interrogating portions of the bit plane to supply the algorithm with sufficient information to distinguish between a true edge, an already filled interior, and artifacts of the line drawing algorithm.
An efficient polygonal contour filling algorithm employs the concept of inverting pixels between edges of the polygon being processed. Such an algorithm is described in The Edge Flag Algorithm--A Fill Method For Raster Scan Displays, Ackland et al., IEEE Transactions On Computers, Vol. C-30, No. 1, Jan. 1981, pp. 41-47 and Efficient Polygon-Filling Algorithms For Raster Displays, Dunlavey, ACM Transactions On Graphics, Vol. 2, No. 4, Oct. 1983, pp. 264-273. Both Ackland et al. and Dunlavey describe a polygonal fill algorithm wherein pixels in the interior of a polygon are turned on by inverting an edge pixel and carrying the inversion action across the polygon until a bit map edge is experienced, at which point the inversion process is terminated. Neither Dunlavey or Ackland et al. focus upon edge representation problems that occur in the image as a result of the inversion-fill procedure. More precisely, they do not address how pixels at edge intersections are to be handled so as to avoid "splinters" from appearing across a page. If two polygon edges intersect at a common pixel location, the last pixel (or pixel step) of one edge will overlap a first pixel of the next edge. Thus, according to the prior art inversion procedure, pixels that extend in the scan direction from the common overlapping pixel are inverted and then re-inverted, as each of the succeeding pixels that comprise the overlapping pixel are processed. This action can create a "splinter" or a very narrow "non-filled" line that extends across the page.
In pixel raster-graphics systems it is often required that vectors be drawn having greater than minimum pixel widths. Some prior art printing devices with limited graphics capability draw such vectors by using fonts containing short segments. Such representations often appear to have "stepped" edges, the degree of stepping dependent upon the slant angle of the line. When grey scales are available, it is possible to achieve an "anti-aliasing" effect by placing grey pixels at the boundaries of such vectors so as to make them appear smoother. While anti-aliasing can improve the appearance of vectors, its techniques are applicable to only certain types of output devices.
If a vector of greater than minimum thickness is either vertically or horizontally oriented, there is no problem in representing it on a pixel grid of finite resolution. As soon as such a vector is rotated, however, the connection of points to define the vector outline poses a number of problems. Even when the end points of a vector lie exactly on the pixel grid, if the vector is oriented at an angle to the grid, portions of the vector will lie fractionally between two grid points.
A current method used to find the outline of a "fat" vector, entails applying half of the vector width to the vector's center line to find one vertex of a rectangle that represents the vector. Then, the full width of the vector is applied to the newly found vertex to find the other corner vertices of the rectangle. This action is accomplished by using sines and cosines to project the rotated vector onto an x,y co-ordinate system. A problem with this technique is that the pixel representations of the ends of the rectangle becomes distorted and often results in non-orthogonal ends for the vector.
Various methods have been proposed to handle representations of fat vectors on raster-graphics pixels displays. "Digitized Brush Trajectories", Hobby, Report No. STAN-CS-85-1070, Department of Computer Science, Stanford University (1985) discloses a number of techniques for representing vector "pen-widths". Among such techniques, Hobby suggests (1) the use of polygonal pens having discrete shapes for constructing representations of vectors of various widths or (2) the building of envelopes with integer offsets to accomplish the same end.
A further description of the use of polygonal pens, as described by Hobby, can be found in "Rendering Fat Lines On A Raster Grid", by Wallace, Graphics Gems, Glassner, Editor, Academic Press, Inc., San Diego, Calif. 92101 (1990), pp. 114-120. Wallace points out that if a line geometry is formulated using an Euclidean metric for line width (a perfectly circular pen instead of a polygon with integer "diameters"), not only does the calculation of x-directed spans require square roots, but the results are inferior to the integer based polygonal approach suggested by Hobby.
Another problem in raster-scan pixel images involves which pixels to "turn-on" at edge intersections. If the choice is not carefully made, such edge intersections exhibit "bumps" where errant pixels distort the intersection's representation.
It is therefore an object of this invention to provide an improved method for representing raster graphics images.
It is another object of this invention to provide an improved polygonal fill procedure for a raster- graphics pixel display wherein edge intersections are handled so as to prevent errant splinters.
It is yet another object of this invention to provide an improved raster-graphics imaging system for representing vectors of greater than minimum thickness.
It is still another object of this invention to provide an improved raster-graphics pixel display system wherein ON pixels resident at an intersection of two edges are chosen so as to best represent the intersection.